from typing import *


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            m = ((r - l) >> 1) + l  # 预计移动的数量
            w = n - m  # 不能移动的数量
            b = False
            cnt = Counter()
            tot = 0
            j = 0
            for i, v in enumerate(nums):
                cnt[v] += 1
                if cnt[v] == 1:
                    tot += 1
                if tot == w:
                    ij = i - j + 1
                    rest = j + ij - w + n - 1 - i
                    if rest >= nums[i] - nums[j] + 1 - w:
                        b = True
                        break
                    while tot == w:
                        cnt[nums[j]] -= 1
                        if cnt[nums[j]] == 0:
                            tot -= 1
                        j += 1
            if b:
                r = m
            else:
                l = m + 1
        return l


s = Solution()
print(s.minOperations([1, 2, 3, 5, 6]))
